// File:       vectorbool.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ vector<bool> specialization

// Change log:
//  11/01/97   v. 1.00
//  22/01/97   Bug fix: forgot self-assignment check in operator=().

#include "vectorbool.h"

#include "algorithm.h"

#include "vector.c++"


// Implementation of vector_bool

#define reference             vector_bool_reference
#define const_reference       bool
#define iterator              vector_bool_iterator
#define const_iterator        vector_bool_const_iterator
#define size_type             size_t
#define difference_type       ptrdiff_t
#define value_type            bool
#define rev_iterator          reverse_iterator<iterator, value_type, reference>
#define const_rev_iterator    reverse_iterator<const_iterator, value_type, const_reference>

vector_bool::vector_bool()
  : size_(0)
  {}

vector_bool::vector_bool(size_type n, bool value)
  : size_(0)
  { insert(begin(), n, value); }

vector_bool::vector_bool(bool const* first, bool const* last)
  : size_(0)
  { insert(begin(), first, last); }

vector_bool::vector_bool(vector_bool const& rhs)
  : base_(rhs.base_),
    size_(rhs.size_)
  {}

vector_bool::~vector_bool()
  {}

const_iterator vector_bool::begin() const
  { return const_iterator(this, 0); }

const_iterator vector_bool::end() const
  { return const_iterator(this, size_); }

const_rev_iterator vector_bool::rbegin() const
  { return const_rev_iterator(end()); }

const_rev_iterator vector_bool::rend() const
  { return const_rev_iterator(begin()); }

size_type vector_bool::find(bool b, size_type pos) const
  {
    if(pos >= size_)
      return npos;

    unsigned long none = (b ? 0 : 0xffffffff);
    size_type bit = pos&31;
    unsigned long const* i = base_.begin()+(pos>>5);
    unsigned long w = *i>>bit;

    if(w == (none>>bit))
    {
      while(++i != base_.end() && *i == none);

      if(i == base_.end())
        return npos;

      w = *i;
      bit = 0;
    }

    if(!b)
      w = ~w;

    if((w<<16) == 0)        { bit += 16; w >>= 16; }
    if((w&0x000000ff) == 0) { bit += 8; w >>= 8; }
    if((w&0x0000000f) == 0) { bit += 4; w >>= 4; }
    if((w&0x00000003) == 0) { bit += 2; w >>= 2; }
    if((w&0x00000001) == 0) { bit += 1; }

    pos = ((i-base_.begin())*32)+bit;

    return (pos < size_ ? pos : npos);
  }

size_type vector_bool::rfind(bool b, size_type pos) const
  {
    if(pos == 0)
      return npos;

    if(pos >= size_)
      pos = size_;

    --pos;

    unsigned long none = (b ? 0 : 0xffffffff);
    size_type bit = pos&31;
    unsigned long const* i = base_.begin()+(pos>>5);
    unsigned long w = *i<<(31-bit);

    if(w == (none<<(31-bit)))
    {
      while(i != base_.begin() && (w = *--i) == none);

      if(w == none && i == base_.begin())
        return npos;

      bit = 31;
    }

    if(!b)
      w = ~w;

    if((w>>16) == 0)        { bit -= 16; w <<= 16; }
    if((w&0xff000000) == 0) { bit -= 8; w <<= 8; }
    if((w&0xf0000000) == 0) { bit -= 4; w <<= 4; }
    if((w&0xc0000000) == 0) { bit -= 2; w <<= 2; }
    if((w&0x80000000) == 0) { bit -= 1; }

    pos = ((i-base_.begin())*32)+bit;

    return (pos < size_ ? pos : npos);
  }

size_type vector_bool::max_size() const
  { return base_.max_size()*32; }

size_type vector_bool::capacity() const
  { return base_.capacity()*32; }

size_type vector_bool::count() const
  {
    size_type result = 0;

    for(int i = 0; i < base_.size(); ++i)
    {
      unsigned long word = base_[i];

      word = (word&0x55555555)+((word>>1)&(0x55555555));
      word = (word&0x33333333)+((word>>2)&(0x33333333));
      word = (word&0x07070707)+((word>>4)&(0x07070707));
      word = (word&0x000F000F)+((word>>8)&(0x000F000F));
      word = (word&0x0000001F)+((word>>16)&(0x0000001F));
      result += int(word);
    }

    return result;
  }

const_reference vector_bool::operator[](size_type n) const
  { return ((base_[n>>5]>>(n&31))&1) != 0; }

const_reference vector_bool::at(size_type n) const
  { return ((base_[n>>5]>>(n&31))&1) != 0; }

vector_bool& vector_bool::operator=(vector_bool const& rhs)
  {
    if(this == &rhs)
    {
      base_ = rhs.base_;
      size_ = rhs.size_;
    }

    return *this;
  }

void vector_bool::assign(bool const* first, bool const* last)
  {
    clear();
    insert(begin(), first, last);
  }

void vector_bool::assign(size_type n, bool t)
  {
    clear();
    insert(begin(), n, t);
  }

iterator vector_bool::begin()
  { return iterator(this, 0); }

iterator vector_bool::end()
  { return iterator(this, size_); }

rev_iterator vector_bool::rbegin()
  { return rev_iterator(end()); }

rev_iterator vector_bool::rend()
  { return rev_iterator(begin()); }

void vector_bool::resize(size_type sz, bool c)
  {
    int change = sz-size();

    if(change > 0)
      insert(end(), change, c);
    else
      erase(begin()+sz, end());
  }

void vector_bool::reserve(size_type n)
  {
    if(capacity() >= n)
      return;

    base_.reserve((n+31)&31);
  }

reference vector_bool::operator[](size_type n)
  { return vector_bool_reference(this, n); }

reference vector_bool::at(size_type n)
  { return vector_bool_reference(this, n); }

reference vector_bool::front()
  { return vector_bool_reference(this, 0); }

reference vector_bool::back()
  { return vector_bool_reference(this, size_-1); }

void vector_bool::push_back(bool x)
  { insert(end(), 1, x); }

void vector_bool::pop_back()
  { erase(end(), end()+1); }

iterator vector_bool::insert(iterator position, bool x)
  {
    insert(position, 1, x);
    return position;
  }

void vector_bool::insert(iterator position, size_type n, bool x)
  {
    base_.resize((size_+31)&31, 0);
    size_ += n;

#ifdef PROBLEM_VECTORBOOL
    for(size_type i = size_-n; i > position.pos_;)
    {
      --i;
      at(i+n) = at(i);
    }
#else
    copy_backward(position, end()-n, end());
#endif

    fill_n(position, n, x);
  }

void vector_bool::insert(iterator position, bool const* first, bool const* last)
  {
    size_type n = last-first;

    base_.resize((size_+31)&31, 0);
    size_ += n;

#ifdef PROBLEM_VECTORBOOL
    for(size_type i = size_-n; i > position.pos_;)
    {
      --i;
      at(i+n) = at(i);
    }
#else
    copy_backward(position, end()-n, end());
#endif

    copy(first, last, position);
  }

void vector_bool::erase(iterator position)
  { erase(position, position+1); }

void vector_bool::erase(iterator first, iterator last)
  {
#ifdef PROBLEM_VECTORBOOL
    ptrdiff_t n = last-first;

    for(size_type i = last.pos_; i < size_; ++i)
      at(i-n) = at(i);
#else
    copy(last, end(), first);
#endif

    size_ -= last-first;
    base_.resize((size_+31)&31, 0);

    clear_overflow();
  }

void vector_bool::swap(vector_bool& x)
  {
    base_.swap(x.base_);
    ::swap(size_, x.size_);
  }

void vector_bool::swap(reference x, reference y)
  {
    bool tmp = x;
    x = y;
    y = tmp;
  }

void vector_bool::clear()
  {
    base_.clear();
    size_ = 0;
  }

void vector_bool::flip()
  {
    if(size_ == 0)
      return;

    for(unsigned long* i = base_.begin(); i != base_.end(); ++i)
      *i = ~*i;

    clear_overflow();
  }

bool vector_bool::test(size_t pos) const
  { return (((base_[pos>>5])>>(pos&31))&1) == 1; }

void vector_bool::set(size_type pos, bool b)
  {
    unsigned long& word = base_[pos>>5];
    unsigned long bit = 1<<(pos&31);

    if(b)
      word |= bit;
    else
      word &= ~bit;
  }

void vector_bool::flip(size_type pos)
  { base_[pos>>5] ^= (1<<(pos&31)); }

void vector_bool::clear_overflow()
  {
    if((size_&31) != 0)
    {
      unsigned long mask = 0xffffffff<<(size_&31);
      base_[((size_+31)>>5)-1] &= ~mask;
    }
  }

#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef size_type
#undef difference_type
#undef value_type
#undef rev_iterator
#undef const_rev_iterator


// Implementation of vector_bool free_fns

bool operator==(vector_bool const& lhs, vector_bool const& rhs)
{
  return lhs.size_ == rhs.size_ && lhs.base_ == rhs.base_;
}

bool operator< (vector_bool const& lhs, vector_bool const& rhs)
{
  return lhs.base_ < rhs.base_;
}


// Implementation of vector_bool_const_iterator

bool vector_bool_const_iterator::operator*() const
  { return base_->at(pos_); }

bool vector_bool_const_iterator::operator[](ptrdiff_t n) const
  { return base_->at(pos_+n); }

